package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author qidi
 * @date 2022-01-04 08:52:36
 */
class Q0100_SameTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            Deque<TreeNode> dp = new ArrayDeque<>();
            Deque<TreeNode> dq = new ArrayDeque<>();
            while (p != null && q != null || !dq.isEmpty() && !dp.isEmpty()) {
                if (p != null && q != null) {
                    dp.push(p);
                    dq.push(q);
                    p = p.left;
                    q = q.left;
                } else {
                    TreeNode ptop = dp.pop();
                    TreeNode qtop = dq.pop();
                    if (ptop.val != qtop.val ||
                            ptop.left == null && qtop.left != null ||
                            ptop.left != null && qtop.left == null ||
                            ptop.right == null && qtop.right != null ||
                            ptop.right != null && qtop.right == null
                    ) {
                        return false;
                    }
                    p = ptop.right;
                    q = qtop.right;
                }
            }
            if (dp.size() != 0 || dq.size() != 0 || q != null || p != null) return false;

            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0100_SameTree().new Solution();
        BTreeUtil util = BTreeUtil.getInstance();
        TreeNode q = util.generateFromArray(1, 2, 3);
        TreeNode p = util.generateFromArray(1, null, 3);

        System.out.println(solution.isSameTree(p, q));
    }
}